package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by baoyunfeng on 2018/1/31.
 */
public class Three_Sum {

    public static void main(String args[]){
        int nums[] = {-1, 0, 1, 2, -1, -4};
        sort(nums);
        for(int i = 0 ;i <nums.length;i++){
            System.out.print(nums[i]+" ");
        }
        System.out.println(" ");
        List<List<Integer>> lists = threeSum(nums);
        for(int i = 0 ;i <lists.size();i++){
            for(int j = 0 ; j< lists.get(i).size();j++){
                System.out.print(lists.get(i).get(j)+" ");
            }
            System.out.println(" ");
        }

    }


    public static List<List<Integer>> threeSum(int[] nums) {
        for(int i = 0 ;i<nums.length;i++){
            for(int j = 0 ; j< nums.length-i-1;j++){
                if(nums[j]>nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }

        List<List<Integer>> list = new ArrayList();


        for(int i = 0 ;i < nums.length-2;i++){
            for(int j = i+1;j<nums.length-1;j++){
                for(int k = j+1; k< nums.length;k++){
                    if(nums[i]+nums[j]+nums[k]==0){
                        boolean flag = false;
                        for(int x = 0 ; x<list.size();x++){
                            if(list.get(x).get(0)==nums[i]&&list.get(x).get(1)==nums[j]&&list.get(x).get(2)==nums[k]){
                                flag = true;
                               break;
                            }
                        }
                        if(!flag){
                            List newList = new ArrayList();
                            newList.add(nums[i]);
                            newList.add(nums[j]);
                            newList.add(nums[k]);

                            list.add(newList);
                        }

                    }
                }
            }
        }


        return list;
    }

    public static void sort(int[] nums){
        for(int i = 0 ;i<nums.length;i++){
            for(int j = 0 ; j< nums.length-i-1;j++){
                if(nums[j]>nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
    }
}
